 /*******************************************************************************
  * Copyright (c) 2000, 2005 IBM Corporation and others.
  * All rights reserved. This program and the accompanying materials
  * are made available under the terms of the Eclipse Public License v1.0
  * which accompanies this distribution, and is available at
  * http://www.eclipse.org/legal/epl-v10.html
  *
  * Contributors:
  * IBM Corporation - initial API and implementation
  *******************************************************************************/
 package org.eclipse.core.internal.dtree;

 import org.eclipse.core.internal.utils.Messages;
 import org.eclipse.core.runtime.IPath;
 import org.eclipse.core.runtime.Path;
 import org.eclipse.osgi.util.NLS;

 /**
  * Data trees can be viewed as generic multi-leaf trees. The tree points to a single
  * rootNode, and each node can contain an arbitrary number of children.<p>
  *
  * <p>Internally, data trees can be either complete trees (DataTree class), or delta
  * trees (<code>DeltaDataTree</code> class). A DataTree is a stand-alone tree
  * that contains all its own data. A <code>DeltaDataTree</code> only stores the
  * differences between itself and its parent tree. This sparse representation allows
  * the API user to retain chains of delta trees that represent incremental changes to
  * a system. Using the delta trees, the user can undo changes to a tree by going up to
  * the parent tree.
  *
  * <p>Both representations of the tree support the same API, so the user of a tree
  * never needs to know if they're dealing with a complete tree or a chain of deltas.
  * Delta trees support an extended API of delta operations. See the <code>DeltaDataTree
  * </code> class for details.
  *
  * @see DataTree
  * @see DeltaDataTree
  */

 public abstract class AbstractDataTree {

     /**
      * Whether modifications to the given source tree are allowed
      */
     private boolean immutable = false;

     /**
      * Singleton indicating no children
      */
     protected static final IPath[] NO_CHILDREN = new IPath[0];

     /**
      * Creates a new empty tree
      */
     public AbstractDataTree() {
         this.empty();
     }

     /**
      * Returns a copy of the receiver, which shares the receiver's
      * instance variables.
      */
     protected AbstractDataTree copy() {
         AbstractDataTree newTree = this.createInstance();
         newTree.setImmutable(this.isImmutable());
         newTree.setRootNode(this.getRootNode());
         return newTree;
     }

     /**
      * Returns a copy of the node subtree rooted at the given key.
      *
      */
     public abstract AbstractDataTreeNode copyCompleteSubtree(IPath key);

     /**
      * Creates a new child in the tree. If a child with such a name exists,
      * it is replaced with the new child
      *
      * @param parentKey key of parent for new child.
      * @param localName name for new child.
      * @exception ObjectNotFoundException
      * parentKey does not exist in the receiver
      * @exception RuntimeException
      * receiver is immutable
      */
     public abstract void createChild(IPath parentKey, String localName);

     /**
      * Creates a new child in the tree. If a child with such a name exists,
      * it is replaced with the new child
      *
      * @param parentKey key of parent for new child.
      * @param localName name for new child.
      * @param object the data for the new child
      * @exception ObjectNotFoundException
      * parentKey does not exist in the receiver
      * @exception RuntimeException
      * receiver is immutable
      */
     public abstract void createChild(IPath parentKey, String localName, Object object);

     /**
      * Creates and returns a new instance of the tree. This is an
      * implementation of the factory method creational pattern for allowing
      * abstract methods to create instances.
      *
      * @return the new tree.
      */
     protected abstract AbstractDataTree createInstance();

     /**
      * Creates or replaces a subtree in the tree. The parent node must exist.
      *
      * @param key key of parent of subtree to create/replace
      * @param subtree new subtree to add to tree
      * @exception RuntimeException receiver is immutable
      */
     public abstract void createSubtree(IPath key, AbstractDataTreeNode subtree);

     /**
      * Deletes a child from the tree.
      *
      * <p>Note: this method requires both parentKey and localName,
      * making it impossible to delete the root node.
      *
      * @param parentKey parent of node to delete.
      * @param localName name of node to delete.
      * @exception ObjectNotFoundException
      * a child of parentKey with name localName does not exist in the receiver
      * @exception RuntimeException
      * receiver is immutable
      */
     public abstract void deleteChild(IPath parentKey, String localName);

     /**
      * Initializes the receiver so that it is a complete, empty tree. The
      * result does not represent a delta on another tree. An empty tree is
      * defined to have a root node with null data and no children.
      */
     public abstract void empty();

     /**
      * Returns the key of a node in the tree.
      *
      * @param parentKey
      * parent of child to retrieve.
      * @param index
      * index of the child to retrieve in its parent.
      * @exception ObjectNotFoundException
      * parentKey does not exist in the receiver
      * @exception ArrayIndexOutOfBoundsException
      * if no child with the given index (runtime exception)
      */
     public IPath getChild(IPath parentKey, int index) {
         /* Get name of given child of the parent */
         String child = getNameOfChild(parentKey, index);
         return parentKey.append(child);
     }

     /**
      * Returns the number of children of a node
      *
      * @param parentKey
      * key of the node for which we want to retreive the number of children
      * @exception ObjectNotFoundException
      * parentKey does not exist in the receiver
      */
     public int getChildCount(IPath parentKey) {
         return getNamesOfChildren(parentKey).length;
     }

     /**
      * Returns the keys of all children of a node.
      *
      * @param parentKey
      * key of parent whose children we want to retrieve.
      * @exception ObjectNotFoundException
      * parentKey does not exist in the receiver
      */
     public IPath[] getChildren(IPath parentKey) {
         String names[] = getNamesOfChildren(parentKey);
         int len = names.length;
         if (len == 0)
             return NO_CHILDREN;
         IPath answer[] = new IPath[len];

         for (int i = 0; i < len; i++) {
             answer[i] = parentKey.append(names[i]);
         }
         return answer;
     }

     /**
      * Returns the data of a node.
      *
      * @param key
      * key of node for which we want to retrieve data.
      * @exception ObjectNotFoundException
      * key does not exist in the receiver
      */
     public abstract Object getData(IPath key);

     /**
      * Returns the local name of a node in the tree
      *
      * @param parentKey
      * parent of node whose name we want to retrieve
      * @param index
      * index of node in its parent
      * @exception ObjectNotFoundException
      * parentKey does not exist in the receiver
      * @exception ArrayIndexOutOfBoundsException
      * if no child with the given index
      */
     public String getNameOfChild(IPath parentKey, int index) {
         String childNames[] = getNamesOfChildren(parentKey);
         /* Return the requested child as long as its in range */
         return childNames[index];
     }

     /**
      * Returns the local names for the children of a node
      *
      * @param parentKey
      * key of node whose children we want to retrieve
      * @exception ObjectNotFoundException
      * parentKey does not exist in the receiver
      */
     public abstract String [] getNamesOfChildren(IPath parentKey);

     /**
      * Returns the root node of the tree.
      *
      * <p>Both subclasses must be able to return their root node. However subclasses
      * can have different types of root nodes, so this is not enforced as an abstract
      * method
      */
     AbstractDataTreeNode getRootNode() {
         throw new AbstractMethodError (Messages.dtree_subclassImplement);
     }

     /**
      * Handles the case where an attempt was made to modify
      * the tree when it was in an immutable state. Throws
      * an unchecked exception.
      */
     static void handleImmutableTree() {
         throw new RuntimeException (Messages.dtree_immutable);
     }

     /**
      * Handles the case where an attempt was made to manipulate
      * an element in the tree that does not exist. Throws an
      * unchecked exception.
      */
     static void handleNotFound(IPath key) {
         throw new ObjectNotFoundException(NLS.bind(Messages.dtree_notFound, key));
     }

     /**
      * Makes the tree immutable
      */
     public void immutable() {
         immutable = true;
     }

     /**
      * Returns true if the receiver includes a node with the given key, false
      * otherwise.
      *
      * @param key
      * key of node to find
      */
     public abstract boolean includes(IPath key);

     /**
      * Returns true if the tree is immutable, and false otherwise.
      */
     public boolean isImmutable() {
         return immutable;
     }

     /**
      * Returns an object containing:
      * - a flag indicating whether the specified node was found
      * - the data for the node, if it was found
      * @param key
      * key of node for which we want to retrieve data.
      */
     public abstract DataTreeLookup lookup(IPath key);

     /**
      * Returns the key of the root node.
      */
     public IPath rootKey() {
         return Path.ROOT;
     }

     /**
      * Sets the data of a node.
      *
      * @param key
      * key of node for which to set data
      * @param data
      * new data value for node
      * @exception ObjectNotFoundException
      * the nodeKey does not exist in the receiver
      * @exception IllegalArgumentException
      * receiver is immutable
      */
     public abstract void setData(IPath key, Object data);

     /**
      * Sets the immutable field.
      */
     void setImmutable(boolean bool) {
         immutable = bool;
     }

     /**
      * Sets the root node of the tree.
      *
      * <p>Both subclasses must be able to set their root node. However subclasses
      * can have different types of root nodes, so this is not enforced as an abstract
      * method
      */
     void setRootNode(AbstractDataTreeNode node) {
         throw new Error (Messages.dtree_subclassImplement);
     }
 }

